import random
import math

def assign_cluster(x, centroids):
    min_distance = float('inf')
    closest_centroid = 0

    for i, centroid in enumerate(centroids):
        distance = 0.0
        for j in range(len(x)):
            distance += (x[j] - centroid[j]) ** 2
        distance = math.sqrt(distance)

        if distance < min_distance:
            min_distance = distance
            closest_centroid = i

    return closest_centroid


def Kmeans(data, k, epsilon=1e-4, max_iterations=100):
    if not data:
        return [], []

    n_samples = len(data)
    n_features = len(data[0])

    centroids = []
    used_indices = set()

    while len(centroids) < k:
        idx = random.randint(0, n_samples - 1)
        if idx not in used_indices:
            centroids.append(data[idx][:])
            used_indices.add(idx)

    for iteration in range(max_iterations):
        labels = [assign_cluster(point, centroids) for point in data]

        new_centroids = []
        for i in range(k):
            cluster_points = [point for j, point in enumerate(data) if labels[j] == i]

            if cluster_points:
                new_centroid = [0.0] * n_features
                for point in cluster_points:
                    for dim in range(n_features):
                        new_centroid[dim] += point[dim]

                for dim in range(n_features):
                    new_centroid[dim] /= len(cluster_points)
                new_centroids.append(new_centroid)
            else:
                new_centroids.append(centroids[i][:])

        max_shift = 0.0
        for i in range(k):
            shift = 0.0
            for dim in range(n_features):
                shift += (new_centroids[i][dim] - centroids[i][dim]) ** 2
            max_shift = max(max_shift, math.sqrt(shift))

        centroids = new_centroids

        if max_shift < epsilon:
            break

    return centroids, labels